package com.example.javamaday.graph;

import java.util.Stack;

/**
 * 拓扑排序实现
 */
public class TopoLogical {

    private Stack<Integer> order;

    public TopoLogical(Digraph digraph) {
        DirectedCycle cycle = new DirectedCycle(digraph);
        if (!cycle.hasCycle()) {
            DepthFirstOrder depthFirstOrder = new DepthFirstOrder(digraph);
            order = depthFirstOrder.reversePost();
        }
    }

    // 图中是否存在环
    private boolean isCycle() {
        return order == null;
    }

    // 获取拓扑排序的结果
    public Stack<Integer> orderResult() {
        return order;
    }

    public static void main(String[] args) {
        Digraph digraph = new Digraph(6);
        digraph.addEdge(0, 2);
        digraph.addEdge(0,3);
        digraph.addEdge(2, 4);
        digraph.addEdge(3,4);
        digraph.addEdge(4, 5);
        digraph.addEdge(1,3);

        TopoLogical topoLogical = new TopoLogical(digraph);
        Stack<Integer> orderResult = topoLogical.orderResult();
        for (Integer w : orderResult) {
            System.out.println(w);
        }
    }

}
